\section{Implementation} \label{sec:implementation}

Our implementation (written in Java) includes three components: regression simulator, test selection,
and test augmentation.

To simulate regression in a policy, 
we used three types of policy change types; $RMR$ (Rule Removal), $RA$ (Rule Addition), and $RDC$ (Rule Decision Change). For $RMR$, given a randomly selected rule in a policy $P$,
the regression simulator removes the rule. For RDC,
given a randomly selected rule in a policy $P$, the regression simulator changes
the decision of the rule.
For $RA$, the regression simulator adds a randomly generated
rule with random attributes collected from $P$ in a random place.
The simulator injects (i.e., mutates) more than one type of changes to $P$ for simulating
regression on $P$.
Given $n$ number of requests, the regression simulator analyzes a policy and injects $n$ changes
into the policy. Among three policy change types, $RA$ is the most flexible
because rules can be composed of any combination of randomly selected attributes.

We next describe rule-test correlation and request recording step in the test-selection
component. 
For the test-selection technique based on mutation analysis technique,
our test-selection component first mutates a rule with RDC in turn. 
Then, the component executes all of test cases for each mutated policy, and
finds rule-test correlation by monitoring 
whether test cases expose different behaviors of an original policy and its mutated policy.
For the test-selection technique based on coverage analysis technique,
the component finds rule-test correlation by executing all of test cases at once and monitoring
which rules are evaluated for a given test case. For the test-selection technique based on recorded request evaluation,
the component logs all requests issued from given test cases.

For change impact analysis, the component leverages an existing policy verification tool called Margrave~\cite{fisler05:verification}. 
Given two versions of policies, $P$ and $P'$, 
the component uses the generic APIs of Margrave to
print out all the changed policy behaviors (i.e., semantic policy changes).
%Our first and second test-selection techniques analyze the results of Margrave and
%find the rules $R_i$ impacted by policy changes.
%Our third test-selection technique does not require change impact analysis. The
%component evaluates requests against $P$ and $P'$ to reveal different evaluated decisions.

The test-augmentation component compares
not-covered policy behaviors $rs_1$ and requests $rs_2$ issued
from existing test cases. The component analyzes the comparison results and classifies
the results into one of our predefined test-augmentation types. 
 



